/*
 * @lc app=leetcode id=39 lang=cpp
 *
 * [39] Combination Sum
 */
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        sort(candidates.begin(), candidates.end());

        vector<int> dq;
        dfs(candidates, 0, target, dq, ret);

        return ret;
    }

    void dfs(vector<int>& candidates, int idx, int target, vector<int> dq, vector<vector<int>>& ret) {

        if (target == 0) {
            ret.push_back(dq);
            return ;
        }

        if (idx == candidates.size() || target < 0) {
            return;
        }

        auto v = candidates[idx];
        dq.push_back(v);
        dfs(candidates, idx, target-v, dq, ret);
        dq.pop_back();
        dfs(candidates, idx+1, target, dq, ret);
    }
};

